package ee.homework.second;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class BinaryTree {

	private Node root;

	public BinaryTree() {
		root = null;
	}

	public static void main(String[] args) {
		BinaryTree tree = new BinaryTree();
		tree.readFile();
		tree.preOrderTreeWalk();
		tree.inOrderTreeWalk();
		tree.postOrderTreeWalk();
		System.out.println("Binary tree maximum depth: " + tree.maxDepth());
		tree.printWidth();
		System.out.print("Parenthesised tree: ");
		tree.parenthesisedTree();
		System.out.println("\nSize of the tree: " + tree.treeSize());
	}

	/**
	 * Nested Node class
	 * 
	 * @author Kaarel Hanson
	 * 
	 */
	private class Node {

		private Node leftChild;
		private Node rightChild;
		private String key;

		public Node(String key) {
			this.key = key;
		}
	}

	public void insert(Node newNode) {
		root = insert(root, newNode);
	}

	public Node insert(Node parent, Node newNode) {
		if (parent == null || parent.key.equals(newNode.key)) {
			parent = newNode;
		} else {
			if (parent.leftChild != null) {
				parent.leftChild = insert(parent.leftChild, newNode);
			}
			if (parent.rightChild != null) {
				parent.rightChild = insert(parent.rightChild, newNode);
			}
		}
		return parent;
	}

	public int maxDepth() {
		return maxDepth(root) - 1;
	}

	public int treeSize() {
		return treeSize(root);
	}

	public int treeSize(Node node) {
		if (node == null) {
			return 0;
		}
		return treeSize(node.leftChild) + treeSize(node.rightChild) + 1;
	}

	private int maxDepth(Node node) {
		if (node == null) {
			return 0;
		} else {
			int lDepth = maxDepth(node.leftChild);
			int rDepth = maxDepth(node.rightChild);
			return Math.max(lDepth, rDepth) + 1;
		}
	}

	public void printWidth() {
		int depth = maxDepth() + 1;
		for (int i = 1; i <= depth; i++) {
			System.out.println("Level: " + i + ", width: "
					+ treeWidth(root, 1, i));
		}
	}

	public int treeWidth(Node node, int initial, int level) {
		if (node == null) {
			return 0;
		} else {
			if (initial == level) {
				return 1;
			} else {
				int left = treeWidth(node.leftChild, initial + 1, level);
				int right = treeWidth(node.rightChild, initial + 1, level);
				return left + right;
			}
		}
	}

	public void preOrderTreeWalk() {
		System.out.print("Preorder treewalk: ");
		preOrderTreeWalk(root);
		System.out.println();
	}

	private void preOrderTreeWalk(Node parent) {
		if (parent != null) {
			System.out.print(parent.key + " ");
			preOrderTreeWalk(parent.leftChild);
			preOrderTreeWalk(parent.rightChild);
		}
	}

	public void inOrderTreeWalk() {
		System.out.print("Inorder treewalk: ");
		inOrderTreeWalk(root);
		System.out.println();
	}

	private void inOrderTreeWalk(Node parent) {
		if (parent != null) {
			inOrderTreeWalk(parent.leftChild);
			System.out.print(parent.key + " ");
			inOrderTreeWalk(parent.rightChild);
		}
	}

	public void postOrderTreeWalk() {
		System.out.print("Postorder treewalk: ");
		postOrderTreeWalk(root);
		System.out.println();
	}

	private void postOrderTreeWalk(Node parent) {
		if (parent != null) {
			postOrderTreeWalk(parent.leftChild);
			postOrderTreeWalk(parent.rightChild);
			System.out.print(parent.key + " ");
		}
	}

	public void parenthesisedTree() {
		parenthesisedTree(root);
	}

	private void parenthesisedTree(Node parent) {
		if (parent != null) {
			System.out.print("(" + parent.key);
			parenthesisedTree(parent.leftChild);
			parenthesisedTree(parent.rightChild);
			System.out.print(")");
		}
	}

	public void readFile() {
		try {
			BufferedReader reader = new BufferedReader(new FileReader(new File(
					"data\\binaryTree.txt")));

			String line = null;
			String[] nodeList = null;
			while ((line = reader.readLine()) != null) {
				if (!line.startsWith("#")) {
					nodeList = line.split("\t");

					Node node = new Node(nodeList[0]);
					if (!nodeList[1].equals("nil"))
						node.leftChild = new Node(nodeList[1]);
					if (!nodeList[2].equals("nil"))
						node.rightChild = new Node(nodeList[2]);

					insert(node);
				}
			}
		} catch (IOException e) {
			System.out.println("Error occurred while trying to read file: "
					+ e.getMessage());
		}
	}
}
